package com.wish.datastructure;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description:
 * @Author: wujv ||suliucheng
 * @Date: 2021/4/20 11:18
 * @Version: 首先需要初始化两个栈： 操作符号栈s1 中间结果栈s2 ，顺序遍历 表达式List
 * 如果 指针指向数字，直接进入中间结果栈
 * 如果指向一个运算符，则考虑
 * 如果符号栈中的栈顶元素 是（ 或者符号栈为空，则直接入栈
 * 如果符号栈栈顶的运算符的优先级高于当前指针的运算符，则弹出符号栈的运算符并且push到中间结果栈
 * ，继续比较
 * 如果当前指针指向一个括号
 * 如果是一个（ 则直接入栈，
 * 如果是一个） 则依次弹出符号栈中的元素并且push到中间结果栈，直到遇到 （ ，此时将这一对括号丢弃
 * <p>
 * 遍历到list最后一个元素的时候，将符号栈中的元素依次弹入到中间结果栈，此时中间结果栈就是后缀表达式的逆序
 * <p>
 * （如果将中间结果栈中的元素依次弹入到符号栈，符号栈弹出拼接是否就是顺序的后缀表达式？？）
 */
public class MiddleToPostExpression {

    /**
     * 初始化一个符号栈,一个结果栈
     */
    private Stack stackSign = new Stack(10);
    private Stack stackResult = new Stack(50);

    private String left = "(";
    private String right = ")";

    private String signs = "/*+-";


    public List<String> translate(List<String> middleExpressionList) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < middleExpressionList.size(); i++) {
            String indexSign = middleExpressionList.get(i);
            if (isNum(indexSign)) {
                stackResult.push(indexSign);
            } else if (isSign(indexSign)) {
                operateStackIfSign(indexSign);
            } else if (left.equals(indexSign)) {
                stackSign.push(indexSign);
            }else if(right.equals(indexSign)){
                while(true){
                    if(stackSign.cloneTop().equals(left)){
                        break;
                    }
                    stackResult.push(stackSign.pop());
                }
                stackSign.pop();
            }

        }
        while (true) {
            if (stackSign.stackIsEmpty()) {
                break;
            }
            stackResult.push(stackSign.pop());
        }
        while (true) {
            if (stackResult.stackIsEmpty()) {
                break;
            }
            list.add(stackResult.pop());
        }
        return list;
    }


    private void operateStackIfSign(String indexSign) {
        if (stackSign.stackIsEmpty() || left.equals(stackSign.cloneTop()) ) {
            stackSign.push(indexSign);
        } else if(currentSign(indexSign)){
            stackResult.push(indexSign);
        }else if(!currentSign(indexSign)){
            stackResult.push(stackSign.pop());
            operateStackIfSign(indexSign);
        }
    }

    /**
     * 站顶运算符的优先级比较高
     *
     * @param indexSign
     * @return
     */
    private boolean currentSign(String indexSign) {
        return getSignLevel(stackSign.cloneTop()) < getSignLevel(stackSign.cloneTop());
    }

    private Integer getSignLevel(String indexSign) {
        int level = 0;
        switch (indexSign) {
            case "+":
            case "-+":
                level = 0;
                break;
            case "/":
            case "*":
                level = 1;
                break;
            default:
                break;
        }
        return level;
    }

    private boolean isSign(String indexSign) {
        if (signs.contains(indexSign)) {
            return true;
        }
        return false;
    }

    private boolean isNum(String indexSign) {
        try {
            Double.parseDouble(indexSign);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}
